package real.unknown.sort;
import java.util.*;
import org.junit.Test;
import utils.ArrayGenerator;

/* 
    实现一个大根堆，两个过程： a、构建堆 b、弹出堆顶数据
*/

public class BigTopHeap {
    private int[] nums;
    private int len;

    public BigTopHeap(int[] nums) {
        this.nums = nums;
        this.len = nums.length;
        initHeap();
    }

    public void initHeap() {
        int len = nums.length;
        for (int i = len / 2; i >= 0; i--) {
            int max = i, left = 2 * i + 1, right = 2 * i + 2;
            if (left < len && nums[left] > nums[max]) {
                max = left;
            }
            if (right < len && nums[right] > nums[max]) {
                max = right;
            }
            //父节点小于子树节点，与较大的子树节点交换
            if (max != i) {
                swap(nums, i, max);
                fix(len, max);
            }
        }
    }

    public void fix(int len, int start) {
        int i = start;
        while (i < len) {
            int max = i, left = 2 * i + 1, right = 2 * i + 2;
            if (left < len && nums[left] > nums[max]) {
                max = left;
            }
            if (right < len && nums[right] > nums[max]) {
                max = right;
            }
            //父节点小于子树节点，与较大的子树节点交换
            if (max != i) {
                swap(nums, i, max);
                i = max;
            } else return; //已不存在子树大于当前节点，结束修补
        }
    }

    public int removeTop() {
        int res = nums[0];
        if (len == 1) return res;
        swap(nums, 0, len - 1);
        len--;
        fix(len, 0);
        return res;
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void heapSort() {
       int length = nums.length;
       for (int i = 0; i < length; i--) {
           removeTop();
       }
    }

    public String toString() {
        return Arrays.toString(nums);
    }

   public static void main(String[] args) {
        // int[] nums = ArrayGenerator.getArray(100, 10);
        int[] nums = {67, 29, 9, 92, 90, 72, 43, 86, 5, 5};
        System.out.println(Arrays.toString(nums));
        BigTopHeap heap = new BigTopHeap(nums);
        System.out.println(heap);
        // System.out.println(heap.removeTop());
        // System.out.println(heap);
        heap.heapSort();
        System.out.println(heap);
   }
}

